import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Random;

public class Solution {
    public static void main(String[] args) {
        // 1 一次定夺，交给我亲爱的JAVA语言决定！
//        Random random = new Random();
//        if(random.nextInt() % 2 == 0) {
//            System.out.println("留校学习");
//        } else {
//            System.out.println("回家学习");
//        }


    }

    public int maxTaskAssign(int[] tasks, int[] workers, int p, int s) {
        /**
         * 你可以安排的最多任务数目
         * 解题思路：
         *  使用 二分查找答案法 + 单调队列
         *  1, 由题干就可得知最终答案的范围，因为已知每个工人最多只能完成一件任务，那么我们最多可完成的任务数就为 min(m,n)，最少为0
         *      又因为我们若是可以完成n个任务，那么就一定能够完成n-1个任务，故此时就具备了二分查找答案的基本要素
         *      假设我们任选mid，若是可以完成，则表示我们必定可以达成[0,mid]这个区间任意的任务数，故使用二分查找
         *  2, 当我们随机选择mid个任务后，我们此时就要去判定：目前的条件是否能够满足我们去成功匹配mid个任务
         *      策略：为了保证任务可行，于是用上简单的贪心策略，即挑选力量值最大的mid名工人 去 完成 最简单的mid个任务
         * */
        // 1 预处理
        int tasksLength = tasks.length;
        int workersLength = workers.length;
        // -排升序
        Arrays.sort(tasks);
        Arrays.sort(workers);

        // 2 二分查找答案法（二分查找右边界）
        int left = 0;
        int right = Math.min(tasksLength, workersLength);
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(checkEnable(tasks, workers, mid, p, s)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        // 3
        return left;
    }

    private boolean checkEnable(int[] tasks, int[] workers, int k, int p, int s) {
        /**
         * 辅助函数：
         *  用于检查判断所给定的条件是否能够满足完成k件任务
         * */
        // 1 预处理
        int workersLength = workers.length;
        // -准备双端队列
        Deque<Integer> queue = new LinkedList<>();

        // 2 枚举最强壮的工人
        int count = 0;
        int taskIndex = 0;
        for(int i = workersLength - k; i < workersLength; i++) {
            // -1 搜索这个工人可以完成的任务，将其入队
            if(taskIndex < k && workers[i] >= tasks[taskIndex]) {
                queue.offerLast(tasks[taskIndex]);
                taskIndex ++;
            }
            /**
             * -2 判断队列是否为空：
             *  为空：说明这个工人无法通过自己的能力完成任务，必须吃药
             *  不为空：判断是否能成功将首元素出队*/
            if(!queue.isEmpty() && queue.peekFirst() <= workers[i]) {
                // -不为空，且可以成功出队
                queue.pollFirst();
            } else {
                // -为空（需要吃药）
                /**
                 * -3 吃药：
                 *  吃药后再搜索一遍所有可以完成任务（为了找到最大任务，并完成，使其吃药效用最大化）*/
                count ++;
                // -4 搜索吃药后可以完成的任务，找到最大任务，使吃药效用最大化
                while(taskIndex < k && workers[i] + s >= tasks[taskIndex]) {
                    queue.offerLast(tasks[taskIndex]);
                    taskIndex ++;
                }
                // -5 维护队列
                if(!queue.isEmpty() && queue.peekLast() <= workers[i] + s) {
                    // -队列不为空，且当前可以成功匹配，出队
                    queue.pollLast();
                } else {
                    // -队列为空或无法匹配，即是吃药也无可奈何，返回false
                    return false;
                }
            }
        }

        // 3 返回值
        return count <= p;
    }
}
